﻿namespace Leetcode.N0052;
public class Solution
{
    public int TotalNQueens(int n)
    {

        var leftLine = new bool[n * 2 - 1];
        var rightLine = new bool[leftLine.Length];
        var verticalLine = new bool[n];

        var count = 0;
        for (int col = 0; col < n; col++)
        {
            this.SolveNQueens(0, col, leftLine, rightLine, verticalLine, ref count);
        }

        return count;
    }

    private void SolveNQueens(int row, int col, bool[] leftLine, bool[] rightLine, bool[] verticalLine, ref int count)
    {
        var n = verticalLine.Length;
        var leftLineIndex = n + (row - col) - 1;
        var rightLineIndex = row + col;

        if (verticalLine[col] || leftLine[leftLineIndex] || rightLine[rightLineIndex])
        {
            return;
        }

        if (row == n - 1)
        {
            count++;
            return;
        }

        verticalLine[col] = true;
        leftLine[leftLineIndex] = true;
        rightLine[rightLineIndex] = true;

        for (int i = 0; i < n; i++)
        {
            this.SolveNQueens(row + 1, i, leftLine, rightLine, verticalLine, ref count);
        }

        verticalLine[col] = false;
        leftLine[leftLineIndex] = false;
        rightLine[rightLineIndex] = false;
    }

}